package com.example.tencentTrain;

import com.example.linked.ListNode;

/**
 * 编写一个程序，找到两个单链表相交的起始节点。
 */
public class Leetcode160_GetIntersectionNode {
    public static void main(String[] args) {
        ListNode headA = new ListNode(1);
        ListNode headB = headA;
        ListNode res = new Solution().getIntersectionNode(headA, headB);
        System.out.println(res.val);
    }

    static class Solution {
        /**
         * 解法二:双指针
         * 如果两个链表相交，那么相交点之后的长度是相同的
         * 我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。
         *
         * 为此，我们必须消除两个链表的长度差
         *   指针 tmp1 指向 A 链表，指针 tmp2 指向 B 链表，依次往后遍历
         *   如果 tmp1 到了末尾，则 tmp1 = headB 继续遍历
         *   如果 tmp2 到了末尾，则 tmp2 = headA 继续遍历
         *   比较长的链表指针指向较短链表head时，长度差就消除了
         *   如此，只需要将最短链表遍历两次即可找到位置
         *
         * @param headA
         * @param headB
         * @return
         */
        private ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode tmp1 = headA, tmp2 = headB;
            while (tmp1 != tmp2) {
                tmp1 = tmp1 == null ? headB : tmp1.next;
                tmp2 = tmp2 == null ? headA : tmp2.next;
            }
            return tmp1;
        }

        /**
         * 暴力法
         * @param headA
         * @param headB
         * @return
         */
        private ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
            ListNode tmp1 = headA, tmp2 = headB;
            while (tmp1 != null) {

                while (tmp2 != null) {
                    if (tmp1 == tmp2) {
                        return tmp1;
                    }
                    tmp2 = tmp2.next;
                }

                tmp2 = headB;
                tmp1 = tmp1.next;
            }
            return null;
        }

        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            return getIntersectionNode2(headA, headB);
        }
    }
}
